import java.util.List;
import java.util.ArrayList;





public class Test {
    private boolean[] check;
    private List<List<Integer>> list;
    public List<List<Integer>> permute(int[] nums) {
        check = new boolean[nums.length];
        list = new ArrayList<>();
        dfs(nums, new ArrayList<>());
        return list;
    }

    private void dfs(int[] nums, List<Integer> l) {
        if (l.size() == nums.length) {
            list.add(l);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!check[i]) {
                l.add(nums[i]);
                check[i] = true;
                dfs(nums, l);
                //回溯
                check[i] = false;
                l.remove(l.size() - 1);
            }
        }
    }

    private List<String> list1;

    public List<String> binaryTreePaths(TreeNode root) {
        list = new ArrayList<>();
        dfs(root, new StringBuilder());
        return list1;
    }

    private void dfs(TreeNode root, StringBuilder path) {
        StringBuilder sb = new StringBuilder(path);
        sb.append(root.val);
        if (root.left == null && root.right == null) {
            list1.add(sb.toString());
            return;
        }
        sb.append("->");
        if (root.left != null) dfs(root.left, sb);
        if (root.right != null) dfs(root.right, sb);
    }

    private List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        list = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums, 0);
        return list;
    }

    private void dfs(int[] nums, int pos) {
        list.add(new ArrayList<>(path));
        for (int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }


}
